#include <stdio.h>
#include <stdlib.h>

/*
 * 线索二叉树
 */

typedef char ElemType;

typedef enum {link, thread} pointertag;

typedef struct bitrnode
{
    char data;
    struct bitrnode * lchild, * rchild;
    pointertag ltag;
    pointertag rtag;
}bithrnode, *bithrtree;

bithrtree pre;

void createbithrtree(bithrtree * t)
{
    char c;

    scanf("%c", &c);
    if (' ' == c) {
        *t = NULL;
    }
    else {
        *t = (bithrnode *) malloc (sizeof(bithrnode));
        (*t)->data = c;
        (*t)->ltag = link;
        (*t)->rtag = link;
        createbithrtree(&(*t)->lchild);
        createbithrtree(&(*t)->rchild);
    }
}

void inthreading(bithrtree t)
{
    if (t) {
        inthreading(t->lchild);

        if (!t->lchild) {
            t->ltag = thread;
            t->lchild = pre;
        }
        if (!pre->rchild) {
            pre->rtag = thread;
            pre->rchild = t;
        }
        pre = t;

        inthreading(t->rchild);
    }
}

void inorderthreading(bithrtree *p, bithrtree t)
{
    *p = (bithrtree)malloc(sizeof(bithrnode));
    (*p)->ltag = link;
    (*p)->rtag = thread;
    (*p)->rchild = *p;

    if (!t) {
        (*p)->lchild = *p;
    }
    else {
        (*p)->lchild = t;
        pre = *p;
        inthreading(t);
        pre->rchild = *p;
        pre->rtag = thread;
        (*p)->rchild = pre;
    }
}

void main()
{
    bithrtree p, t = NULL;

    createbithrtree(&t);

    inorderthreading(&p, t);
}

/*
 
 ABC  D  E F
 
 */

